import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 27
 * Time: 21:31
 */
//牛客 二叉树中和为某一值的路径(一)
public class Solution4 {
    //法一 官方推荐方法递归
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        }
        return hasPathSum (root.left, sum - root.val) || hasPathSum (root.right, sum - root.val);
    }

    //法二 官方方法非递归（双栈）
    public boolean hasPathSum1 (TreeNode root, int sum) {
        if(root == null) return false;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        s1.push(root);
        s2.push(root.val);
        while (!s1.isEmpty()) {
            TreeNode temp = s1.pop();
            int cur_sum = s2.pop();
            if(temp.left == null && temp.right == null && cur_sum == sum) {
                return true;
            }
            if(temp.left != null) {
                s1.push(temp.left);
                s2.push(cur_sum + temp.left.val);
            }
            if(temp.right != null) {
                s1.push(temp.right);
                s2.push(cur_sum + temp.right.val);
            }
        }
        return false;
    }
}
